package org.czl.tree;

import java.util.Arrays;

public class l1879 {
        int n ;
        public int minimumXORSum(int[] nums1, int[] nums2) {
            n = nums2.length;
            int[] dp = new int[1 << (n + 1)];
            Arrays.fill(dp, 0, dp.length, -1);
            return f(nums1, nums2, (1 << (n + 1)) - 1, dp, 0, 0);
        }

        int f(int[] nums1, int[] nums2, int status, int[] dp, int size, int goal){
            if(size == n - 1){
                for(int i = 1; i <= n; i++){
                    if((status & (1 << i))  != 0){//当前值可以选
                        return nums1[size] ^ nums2[i - 1];
                    }
                }
                return nums1[size] ^ nums2[goal];
            }
            if(dp[status] != -1){
                return dp[status];
            }
            int ans = 0;
            int m = Integer.MAX_VALUE;
            for(int i = 1; i <= n; i++){
                if((status & (1 << i))  != 0){//当前值可以选
                    ans = nums1[size] ^ nums2[i - 1];
                    m = Math.min(f(nums1, nums2, status ^ (1 << i), dp, size + 1, i - 1) + ans, m);
                }
            }
            dp[status] = m;
            return m;
        }

}
